#include <stdio.h>
#include <stdlib.h>

//定义最大顶点数，本常量在定义MGraph结构体的顶点和边时，都必须被用到
#define MVNum 100
typedef enum{FALSE,TRUE} Boolean;

typedef char VerTexType;      //假设顶点的数据类型为字符型 
typedef int ArcType;          //假设边的权值类型为整型 

typedef struct{ 
	VerTexType vexs[MVNum];     //顶点表 
	ArcType arcs[MVNum][MVNum]; //邻接矩阵 
	int vexnum, arcnum;         //图的当前点数和边数 
} MGraph; 



//=========建立邻接矩阵=======
// 参数 G_pp 是尚未被初始化的 (指向 (指向 MGraph 的指针) 的指针)
// 参数 graph_data_filename 是存储如下格式的图数据的文件名（字符串）：
/*
 * 顶点数 边数
 * 顶点名字序列（用a b c d e 等字符命名）
 * a b // 边1
 * a c // 边2
 * d e // 边3
 */
void create_graph(MGraph ** G_pp, char * graph_data_filename)
{
	FILE * fp;
	size_t len = 0; //无符号整数
	ssize_t read;   //long无符号整数
	
	int num_nodes, num_edges;
	*G_pp = (MGraph *)malloc(sizeof(MGraph));
	MGraph *g_pp = *G_pp;
	// 打开由 graph_data_filename变量 指定的文件名
	fp = fopen(graph_data_filename, "r");
	if (fp == NULL)
		printf("文件读取失败\n");//    exit(EXIT_FAILURE);
	// 从文件名由 graph_data_filename 变量所指定的文件里读取顶点数和边数
	// fscanf函数 的用法类似scanf
	fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
	printf("顶点数 ：%d \n 边数： %d\n",num_nodes,num_edges);
	g_pp->vexnum=num_nodes;//定义结构体的点数
	g_pp->arcnum=num_edges;//边数
	
	//定义
	char cx,cy;
	int x,y;
	// 后续的内容读取参考上一句 fscanf 函数
	for (int i = 0; i < num_nodes; ++i) {
		fscanf(fp, "%c ",&g_pp->vexs[i]);
		printf("%c ",g_pp->vexs[i]);
	}
	printf("\n");
	fscanf(fp, "\n",&g_pp->vexs[num_nodes]);
	// 实现开始：可以自行定义变量，但是不要删掉或者更改对fopen和fclose的调用
	//初始化矩阵
	for (int i = 0; i < num_edges; ++i) {
		for (int j = 0; j < num_edges; ++j) {
			g_pp->arcs[i][j]=0;
		}
	}
	//写入矩阵
	printf("------所有边------\n");
	for (int i = 0; i < num_edges; ++i) {
		fscanf(fp, "%c %c\n",&cx,&cy);
		printf("%c %c ",cx,cy);
		x=(int)cx-97;
		y=(int)cy-97;
		g_pp->arcs[x][y]=1;
		printf("\n");
	}
	printf("\n");
	//输出矩阵
	printf("   -----输出矩阵-----\n");
	for (int i = 0; i < num_edges; ++i) {
		for (int j = 0; j < num_edges; ++j) {
			printf("%d  ",g_pp->arcs[i][j]);
		}
		printf("\n");
	}
	// 如上，用fscanf从fp里读取字符
	// 实现结束
	// 关闭打开的文件
	fclose(fp);
}

//========dfs：深度优先遍历的递归算法======
// 参数 G：指向MGraph类型的变量的指针。
// 参数 i: 当前被访问的顶点 i。i是顶点在给出的 顶点名字序列里从0开始的位置编号：比如顶点 b 在顶点序列 a b c d e f中的位置编号是 1。
// 参数 result_sequence: 用于记录在当全局访问顺序为 visited_order 时，被访问的结点名字（字符）。
// 参数 visited_order: 当前顶点被访问的全局顺序
void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{
	int j;
	//   printf("%c",G->vexs[i]);     //访问顶点Vi
	result_sequence[*visited_order]=G->vexs[i];
	*visited_order=*visited_order+1;
	visited[i]=TRUE;             //置已访问标志
	for(j=0;j<G->vexnum;j++){//依次搜索Vi的邻接点
		if(G->arcs[i][j]==1 && ! visited[j]){
			dfs(G,j,visited,result_sequence,visited_order);  //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
		}
	}
}

// ====查找图G的顶点的编号====
// 编号为构建图G时每个顶点的读入顺序，从0开始。
// 查找到指定顶点名字时，返回对应编号；找不到时，返回-1 。
int locate_vertex(MGraph * G, char vertex_name) {
	for (int i = 0; i < G->vexnum; i++) {
		if (G->vexs[i]==vertex_name){
			return i;
		}
	}
	return -1;
}
//===========bfs：广度优先遍历=======
// 参数 G：指向MGraph的指针
// 参数 k: 当前被访问的顶点 k。k是顶点在给出的 顶点名字序列里从0开始的位置编号；比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 visited_sequence: 用于记录在广度优先遍历时，依次被访问的顶点的名字（字符）
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{
	//非递归写法
	int j,i,l=0,m=0;
	char t[MVNum];
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
		visited_sequence[i]=0;
		t[i]=NULL;
	}
	visited_sequence[m]=G->vexs[k];
	t[m]=G->vexs[k];
	l=locate_vertex(G,t[m]);
	visited[l] = TRUE;
	m++;
	for (int g=0; g < G->vexnum;g++) {
		l=locate_vertex(G,t[g]);
		if(locate_vertex(G,t[g])==-1){
			printf("\n");
			return;
		}
		printf("%d,",g);
		for(j=0;j<G->vexnum;j++){//依次搜索Vi的邻接点
			if(G->arcs[l][j]==1 && ! visited[j]){
				visited[j] = TRUE;
				visited_sequence[m]=G->vexs[j];
				t[m]=G->vexs[j];
				m++;
			}else{
				if(G->arcs[j][l]==1 && ! visited[j]){
					visited[j] = TRUE;
					visited_sequence[m]=G->vexs[j];
					t[m]=G->vexs[j];
					m++;
				}
			}
		}
	}
	printf("\n");
}


// 以下 main 函数的实现，供参考。

int main () {
	int i;
	MGraph *G;
	Boolean visited[MVNum];
	
	create_graph(&G,"graph_data.txt"); //建立邻接矩阵
	
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
	}
	char dfs_sequence[MVNum] = {'\0'};
	int visited_order = 0;
	dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
	printf("Print Graph DFS: ");
	printf("%s\n", dfs_sequence);
	printf("\n");
	
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
	}
	char bfs_sequence[MVNum] = {'\0'};
	bfs(G, 0, visited, bfs_sequence); //以序号为3的顶点开始广度优先遍历。应该输出：abcdefgh
	printf("Print Graph BFS: ");
	printf("%s\n", bfs_sequence);
	printf("True Graph BFS:abcdefgh");
	printf("\n");
	
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
	}
	char bfs_sequence2[MVNum] = {'\0'};
	bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
	printf("Print Graph BFS: ");
	printf("%s\n", bfs_sequence2);
	printf("True Graph BFS:dbhaecfg");
	printf("\n");
	
	return 0;
}
